class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int> > dp(prices.size(),vector<int>(5,0));
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for(int i = 1;i < prices.size();i++){
            for(int j = 1;j <= 3;j += 2){
                dp[i][j] = max(dp[i-1][j-1]-prices[i],dp[i-1][j]);
                dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]+prices[i]);
            }
        }
        return dp[prices.size() - 1][4];
    }
};
